// work out factorial of an integer
#ifndef _ALGORITHM_H_
#define _ALGORITHM_H_

#include <math.h>
#include "common.h"

// randomly generate an integer between two numbers, begin <= result < end 
inline
const int Random(const int &begin, const int &end) {
	srand((int)time(0));
	return begin + (int)( (rand() % (end - begin) ));
}

// entrance for factorial
const int factorial(const int &n, bool is_recursion = false);
// recursion mode
const int factorial_recursion(const int &n);
// nonrecursion mode
const int factirial_nrecursion(const int &n);

// entrance for fibonaci
const int fibonaci(const int &n, bool is_recursion = false);
// recursion mode
const int fibonaci_recursion(const int &n);
// nonrecursion mode
const int fibonaci_nrecursion(const int &n);
const int fibonaci_nrecursion_loop(const int &n);

// permutation structure using recursion
template<typename T>
void permutation(T list[], const int &begin, const int &end) {
	// when it comes to the end
	if (begin == end) {
		// do something
		//for (int i = 0; i < end; ++i) cout << list[i];
		//cout << endl;
	}

	for (int i = begin; i <= end; ++i) {
		Swap(list[begin], list[i]);
		permutation(list, begin + 1, end);
		Swap(list[begin], list[i]);
	}
}

// nums of integer division using recursion
const int integer_division(const int &number, const int &max);

// hanoi using recursion
void hanoi(const int &n, const int &src, const int &dest, const int &help);
void move(const int &src, const int &dest);

//binary search the index of target
template<typename T>
int binary_search(T list[], T target, const int &size) {
	int left = 0, right = size - 1;
	while (left <= right) {
		int middle = (left + right) / 2;
		if (list[middle] == target) {
			return middle;
		}

		if (target < list[middle]) {
			right = middle - 1;
		}
		else {
			left = middle + 1;
		}
	}
	// target not found
	return -1;
}

// quick sort ascending
template<typename T>
void quick_sort(T list[], const int &begin, const int &end) {
	if (begin < end) {
		int p = partition(list, begin, end);
		quick_sort(list, begin, p);
		quick_sort(list, p + 1, end);
	}
}

// quick select the kth smallest element in list
template<typename T>
T quick_select(T list[], const int &begin, const int &end, const int &k) {
	if (begin == end) {
		return list[begin];
	}

	int p = partition(list, begin, end);


	if (k <= p) {
		return quick_select(list, begin, p, k);
	}

	// there are j elements smaller
	int j = p - begin + 1;
	return quick_select(list, p + 1, end, k - j);
}

// linear select the kth smallest element in list
// it waits for completing
/*
template<typename T>
T linear_select(T list[], const int &begin, const int &end, const int &k) {
	if (end - begin < 75) {
		// use any kind of sorting method, it doesn't matter
		return quick_select(list, begin, end, k);
	}

	for (int i = 0; i <= (end - begin - 4) / 5; ++i) {
		// select the third smallest element between a[begin + 5 * i] and a[begin + 5 * i + 4]
		quick_sort(list, begin + 5 * i, begin + 5 * i + 4);
		// swap list[p + i] and the result above
		Swap(list[p + i], list[begin + 5 * i + 2]);
	}
	T x = linear_select(list, begin, begin + (end - begin - 4)/5, (end - begin - 4)/10);
}
*/

template<typename T>
int partition(T list[], const int &begin, const int &end) {
	int left = begin, right = end + 1;
	
	// randomly select a element in list
	int i = Random(begin, end);
	Swap(list[begin], list[i]);

	T x = list[begin];
	while (true) {
		while (list[++left] < x && left < end);
		while (list[--right] > x);
		if (left >= right) {
			break;
		}
		Swap(list[left], list[right]);
	}
	Swap(list[begin], list[right]);
	return right;
}

// find point pair with the smallest distance in one dimension array
// the array should be in order
// @params list		element array
// @params left		left edge
// @params right	right edge
//
// @out p1		left element of the closest pair
// @out p2		right element of the closest pair
// @out d		smallest distance
template<typename T>
void closest_pair(T list[], const int &left, const int &right, T &p1, T &p2, T &d) {
	const int size = right - left + 1;
	if (2 == size) {
		T tmp = list[right] - list[left];
		if (tmp < d) {
			p1 = list[left];
			p2 = list[right];
			d = tmp;
		}
		return;
	}

	if (size > 2) {
		// find the median and split the list into two according to it
		int middle = left + size / 2;
		closest_pair(list, left, middle - 1, p1, p2, d);
		closest_pair(list, middle, right, p1, p2, d);

		if (list[middle] - list[middle - 1] < d) {
			p1 = list[middle - 1];
			p2 = list[middle];
			d = list[middle] - list[middle - 1];
		}
	}
}

// longest common subsequence length
void LCSLength(const char *s1, const char *s2, const int &n1, const int &n2, int **lengths, int **tags);

// find subsequence with the largest sum in an one dimension array
int MSSum(const int list[], const int &left, const int &right);
// find subsequence with the largest sum in a two dimension array
// if the declaration of list is const int **list, it means that it can modify list by using the second dimension pointer
int MSSum2(const int * const * list, const int &top, const int &bottom, const int &left, const int &right);
#endif
